package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/two-sum-bsts'>查找两棵二叉搜索树之和(Two Sum BSTs)</a>
 * <p>给出两棵二叉搜索树的根节点 root1 和 root2 ，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。</p>
 * <p>如果可以找到返回 True，否则返回 False。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root1 = [2,1,4], root2 = [1,0,3], target = 5
 *              2                   1
 *            /  \                /  \
 *           1    4              0    3
 *      输出：true
 *      解释：2 加 3 和为 5 。
 *
 *  示例 2：
 *      输入：root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
 *              0                     5
 *            /   \                 /   \
 *          -10    10              1     7
 *                               /  \
 *                              0    2
 *      输出：false
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>每棵树上节点数在 [1, 5000] 范围内。</li>
 *     <li>-10^9 <= Node.val, target <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/16 11:40
 */
public class LC1214TwoSumBSTs_M {
    static class Solution {
        /**
         * BST 二叉搜索树的中序遍历是有序的。使用双指针+中序遍历
         */
        public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            dfs(root1, list1);
            dfs(root2, list2);
            int idx1 = 0;
            int idx2 = list2.size() - 1;
            while (idx1 < list1.size() && idx2 >= 0) {
                int sum = list1.get(idx1) + list2.get(idx2);
                if (sum < target) {
                    ++idx1;
                } else if (sum > target) {
                    idx2--;
                } else {
                    return true;
                }
            }
            return false;
        }


        private void dfs(TreeNode currNode, List<Integer> list) {
            if (currNode == null) {
                return;
            }
            dfs(currNode.left, list);
            list.add(currNode.val);
            dfs(currNode.right, list);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.twoSumBSTs(Generator.buildTree(2, 1, 4), Generator.buildTree(1, 0, 3), 5));
        System.out.println(solution.twoSumBSTs(Generator.buildTree(0, -10, 10), Generator.buildTree(5, 1, 7, 0, 2), 18));
    }
}
